
// topk.h
#ifndef __TOPK_H__
#define __TOPK_H__


#include <algorithm>
#include <cstdio>


template<typename T, int N = 10>
class TopK
{
public:
    TopK():data_(0),size_(0)
    {
        data_ = new T[N];
    }
    ~TopK()
    {
        delete []data_;
        data_ = 0;
        size_ = 0;
    }
    void push_back(T v)
    {
        if(size_ < N)
        {
            data_[size_++] = v;
            if(size_ == N)
            {
                _build_heap();
            }
        }
        else
        {    
            // found some value greater then min(heap top)
            if(v > data_[0])
            {
                data_[0] = v;
                _heap_adjust(0);
            }
        }
    }
    void sort()
    {
        int count = size_;
        for(int i = 0; i < count; ++i)
        {
            T t = data_[0];
            data_[0] = data_[size_ - 1];
            data_[size_ - 1] = t;
            --size_;
            _build_heap();
        }
        size_ = count;
    }
    void p()
    {
        for (int i = 0; i < size_; ++i)
        {
            printf("%d ",data_[i]);
        }
        printf("\n");
    }
private:
    void _heap_adjust(int pos)
    {
        int now_pos = pos;
        while(true)
        {
            int l = now_pos * 2 + 1;
            if(l > size_ -1)
            {
                break;
            }
            int r = now_pos * 2 + 2;
            int min_pos = 0; 
            if(r > size_ - 1)
            {
                min_pos = l;
            }
            else
            {
                min_pos = data_[l] < data_[r] ? l : r;
            }
            if(data_[now_pos] > data_[min_pos])
            {
                std::swap(data_[now_pos],data_[min_pos]);
            }
            now_pos = min_pos;
        }
    }
    void _build_heap()
    {
        for (int i = size_ / 2 - 1; i >= 0; --i)
        {
            _heap_adjust(i);
        }
    } 
private:
    T* data_;
    int size_;
};

/*
int main(int argc, char* argv[]) 
{
    TopK<int> topk;
    for(int i = 0; i < 1000; ++i)
    {
        topk.push_back(i);
    }
    topk.p();
    topk.sort();
    topk.p();
    return 0;
}
*/
#endif //__TOPK_H__